Web log de Serge Boisse
On line depuis 1992 !
Auteur : Serge Boisse
Date : Le 20/07/2023 à 21:07
Résumé : On essaye ici de développer une nouvelle théorie des nombres entiers, et en particulier on cherchera les limites de ces systèmes formels.
Voir aussi: Card(N) est-il fini
complexite
Maths
Une première définition des entiers naturels est extraite de Gödel, Escher, Bach : les Brins d'une Guirlande Eternelle, le merveilleux livre de Douglas Hofstadter, et constitue la base de ce qu'il a appelé la Théorie des Nombres Typographique, ou TNT (!)
Elle utilise neuf symboles :
En outre les lettres
Et voici les cinq axiomes d'une théorie minimale :
Il s'agit d'une théorie minimaliste des entiers naturels : Elle ne dit pas ce qu'est un nombre naturel, mais seulement quelles propriétés il devrait avoir vis a vis de l'adition et de la multiplication.
En fait, au lieu de "nombre", les axiomes pourraient aussi bien définir autre choses, disons, comme Hosftadter, un "Djinn" : On pourrait alors avoir les axiomes suivants :
Ce qui est une théorie légèrement différente : elle ne parle ni de l'addition, ni de la multiplication ! Mais elle comporte un nouvel axiome très puissant, l'axiome de récurrence. Dans cet axiome X représente une propriété applicable aux Djinns.
Comment formaliser tout ceci ? Au moyen des axiomes de Peano !
On les définit classiquement par le système formel inventé par Guiseppe Peano en 1889 : Noter qu'il comporte un symbole de plus :
Les axiomes de Peano supposent aussi que l'on admet celles de la logique :
Pour tous les "prédicats du premier ordre" (c'est à dire contenant éventuellement des variables)
Et voici les axiomes de Peano :
Enfin le célèbre axiome de récurrence :
Les quantificateurs
Cet ensemble est défini à un isomorphisme près : en particulier le nombre
Dans le point (2) le
Les axiomes de Peano définissent les propriétés attendues d'un entier naturel, mais aussi de leur addition et leur multiplication.
Les axiomes ci dessus ne définissent pas d'ordre. Pour cela il faut en ajouter, par exemple
Enfin, le point (8) ci-dessus (qui axiomatise le principe de récurrence) est un schéma d'axiomes, qui représente une infinité dénombrable d'axiomes, un pour chaque formule.
Rien n'empèche bien sûr ensuite de nommer les entités obtenues (les nombres naturels) et posant
Il me semble que cette définition de l'arithmétique laisse de côté la notion de complexité (de Kolmogorov). Par exemple comment faire des récurrences sur des très grands entiers sans préciser combien de pas de recurrence on doit faire, et quid si ce nombre de pas est lui -même un nombre non calculable ?
Le fait est, que pour de très grands entiers, disons
Je cherche une définition des entiers qui aille non du plus petit au plus grand, mais du plus simple au plus complexe.
Les axiomes de Peano présupposent qu'il existe une application successeur
En effet, si on prend en compte des très grands nombres comme ceux que l'on peut obtenir avec la notation de Knuth ou la notation fléchée de Conway, on se rend compte qu'entre deux de ces nombres il existe un vide immense, dans lequel existent (ou pas ?) des nombres dont la seule description, même programmatique, nécessiterait (beaucoup !) plus de pages qu'il n'existe d'atomes dans l'univers !
Enfin, la formulation de Peano oublie deux des fondements de ce que nous entendons intuitivement par arithmétique :
A mon avis on ne peut construire un nombre
Pour moi, les nombres entiers sont comme des perles sur un fil. Le fil est la fonction successeur, les perles (de plus en plus grosses) sont les entiers "issus" d'un très grand entier donné.
L'axiome 2 de Peano
Ce que l'on pourrait traduire par "tout entier non nul doit avoir un prédécesseur". Notons que l'existence signifie "au moins 1".
Que se passerait-il si l'on modifie cet axiome ? On pourrait donc imaginer trois sorte d'aritmétiques "non Péaniènes" dans laquelle un entier pourrait avoir 0, 1 ou plusieurs prédécesseurs, de la mème façon que l'on a construit les géométries non Euclidiennes en modifiant le postulat des parallèles...
En fait, si certains entiers "spéciaux", et rares, n'avaient pas de prédécesseurs (et pas seulement le nombre 0), on se retrouverait devant une théorie qui rappelle la construction des ordinaux...
Et je me demande si certain très grands entiers comme le nombre de Graham, ou TREE(3), ou Ackerman(999) ne sont pas dans ce cas. En effet comment définir leur prédécesseur sans utiliser la définition de la fonction qui les a créé, ni bien sûr la soustraction de 1 ?
cf complexite
un entier, c'est soit 0, soit le résultat d'une fonction primitive récursive numérique appliquée à 0
[définition]
Une fonction primitive récursive numérique est une fonction qui a des arguments entiers (au sens ci-dessus), et dont on peut prouver sans l'exécuter (par l'examen attentif du code de la fonction), qu'elle rendra un résultat en un temps fini quelques soient ses arguments.
Par exemple on peut décrire une telle fonction par un programme écrit dans un langage qui ne comporte aucune instruction while, ni goto, ni d'appels récursifs (c'est à dire qu'une fonction ne peut appeler que des fonctions précédemment définies), et dont les boucles for sont uniquement du style for i in range x où x est un entier précédemment calculé. Ce que Douglas Hofstadter, dans son merveilleux livre "Gödel, Escher, Bach" appelait le langage "BUCLE"
La question, c'est : le nombre d'entiers ainsi définissable est-il fini ?
Bien sûr, le nombre de fonctions primitives récursives numériques ainsi définissable est infini, mais cela ne prouve pas que le le nombre de résultats possible de ces fonctions soit infini !
Les entiers ainsi définis sont donc des entiers calculables, ce qui signifie "calculables en un temps fini et prévisible". En particulier, Les machine de Turing ne correspondent pas à la définition puisque qu'on ne peut pas prévoir s'il elle s'arrèteront.
Une question fascinante est : Est-ce que une machine de Turing qui s'arrête en un temps fini peut produire des résultats qui ne puissent pas être produits par un programme BUCLE ? Je ne sais pas, mais j'ai l'intuition que non.
On va définir une suite d'opérations pour produire des nombres de plus en plus grands :
https://fr.wikipedia.org/wiki/Hi%C3%A9rarchie_de_croissance_rapide
Comme notre propos est de formaliser le dénombrable, on se limitera ici à l'ordinal limite
On définira donc une hiérarchie de fonctions
Définissons maintenant les
ainsi,
o(k,m,n)=(m==0)?1:(k==0)?n+1:(m==1)?o(k-1,n,n):o(k,1,o(k-1,m-1,n))
Et nous arrivons ainsi à une fonction d'Ackerman généralisée
cf
Pour tout ordinal
si
Pour tout ordinal
Mon idée est que tout entier
Je propose que chaque entier soit en réalité un couple (n,k), où n est un entier et k sa complexité. Reste à trouver une axiomatique pour les définir.
On posera
Il faut comprendre que
Pour cela, on définira une fonction
Voici nos axiomes :
Pout tout
Un nombre entier
Et bien sûr c'est pour le point 4 que le bât blesse...
page créée le 18/03/2025 à 15:09modifiée le 01/06/2025 à 15:32
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.